﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DXBase.Structs
{
	/// <summary>
	/// A (spatial) binary search tree for object with a BBox
	/// </summary>
	public class OctTree<T> : SpatialIndex<T, Box3D>
		where T : IHasBounds<Box3D>
	{
		public OctTree(Box3D bounds, int maxDepth = 20)
			: base(bounds, maxDepth)
		{
		}
		public OctTree(Box3D bounds, float res)
			: base(bounds, res)
		{
		}

		public override IList<Box3D> Divide(Box3D b)
		{
			var max = Math.Max(b.Width, Math.Max(b.Height, b.Depth));
			var tresh = 0.65f * max;
			var dx = b.Width;
			var xs = Split(b.X, ref dx, tresh);
			var dy = b.Height;
			var ys = Split(b.Y, ref dy, tresh);
			var dz = b.Depth;
			var zs = Split(b.Z, ref dz, tresh);
			var result = new Box3D[xs.Length * ys.Length * zs.Length];
			int i = 0;
			for (int ix = 0; ix < xs.Length; ix++)
				for (int iy = 0; iy < ys.Length; iy++)
					for (int iz = 0; iz < zs.Length; iz++)
						result[i++] = new Box3D(xs[ix], dx, ys[iy], dy, zs[iz], dz);
			return result;
		}
		static float[] Split(float x, ref float dx, float tresh)
		{
			if (dx >= tresh)
			{
				dx /= 2;
				return new[] { x, x + dx };
			}
			else
			{
				return new[] { x };
			}
		}
	}
}
